• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    Es werden eine Anzahl von Verfahren und Systemen zum effizienten Speichern von Defekte-Speicherplätze-Tabellen offenbart. Ein Vektorquantisierungsverfahren eines Asymmetrische-Verzerrung-Modells und ein Lauflängenquantisierungsverfahren zum Komprimieren einer Defekte-Speicherplätze-Bittabelle, die defekte Speicherplätze in einem Speicher identifiziert, werden bereitgestellt. Da diverse unterschiedliche Komprimierungs-/Entkomprimierungsverfahren für unterschiedliche Typen von Defektverteilungen in einem Speicher geeignet sein können, wird ferner ein Verfahren zum Auswählen des am besten geeigneten Komprimierungs-/Entkomprimierungsverfahrens aus einer Anzahl von Komprimierungs-/Entkomprimierungsverfahren als für eine bestimmte Defektwahrscheinlichkeitsverteilung am besten geeignet bereitgestellt. Schließlich können eine Bittabellenkomprimierung und die Gütefaktormetrik zum Auswählen einer entsprechenden Komprimierungstechnik eine globale Optimierung von Fehlerkorrekturcodes und der Identifizierung von defekten Speicherplätzen ermöglichen.
    公开号:DE102004003353A1
    申请号:DE200410003353
    申请日:2004-01-22
    公开日:2004-12-09
    发明作者:Giovanni Waltham Motta；Erik San Jose Ordentlich；Gadiel Cupertino Seroussi；Marcelo San Jose Weinberger
    申请人:Hewlett Packard Development Co LP；
    IPC主号:G06F12-16
    专利说明:
    [0001] Dievorliegende Erfindung bezieht sich auf Datenspeichervorrichtungenbzw. Speicher und insbesondere auf Datenspeichervorrichtungen zugeordneteDefekte-Speicherplätze-Tabellen bzw. Speichernzugeordnete Defekte-Speicherplätze-Tabellen, die alledefekten Speicherplätzeidentifizieren, so daß auseinem Speicher eine sequentielle Liste von logischen Speicherplätzen, diemit monoton ansteigenden Indizes indexiert sind, erstellt werdenkann, die eine Anzahl von defekten physischen Speicherplätzen bzw.physikalischen Speicherorten umfaßt.
    [0002] Inden letzten Jahren wurden enorme Schritte dahingehend unternommen,neue Technologien zum Speichern von Daten in Datenspeichervorrichtungenbzw. Speichern zu entwickeln. Elektronische Speicherchips mit hoherDichte und hoher Kapazitätsind mittlerweile ohne weiteres und auf kostengünstige Weise erhältlich,und unter Verwendung von Halbleiterfilmen werden neuere dreidimensionalegestapelte elektronische Speichervorrichtungen entwickelt. Ältere Technologienumfassen Magnetplatten, Magnetbänder,und sehr alte Technologien umfassen Kernspeicher und Trommelspeicher.Elektronische und magnetische Speichervorrichtungen weisen allgemeineine sehr großeAnzahl von adressierbaren physischen Speicherplätzen auf, wobei jeder physischeSpeicherplatz in der Lage ist, ein oder mehrere computerlesbareBytes oder Wörterzu speichern, die aus einer feststehenden Anzahl von Bits bestehen,z.B. 8-Bit-Bytes und 32-Bit-Wörter oder 64-Bit-Wörter. DieSpeichereinheiten der untersten Ebene, die allgemein als „Datenspeichereinheiten" bezeichnet werden,könnenhierarchisch in größere Einheitenwie z.B. Plattensektoren oder dreidimensionale Speicherebenen gruppiertwerden. Ein physischer Speicherplatz weist eine oder mehrere Datenspeichereinheitenauf, die durch eine physische Adresse adressiert werden können. Einphysischer Speicherplatz kann auf einem Typ von Speichervorrichtungein computerlesbares Wort sein und kann auf einem anderen Typ von Vorrichtungein Plattensektor sein.
    [0003] Ungeachtetder Technologie kann allgemein eine gewisse Anzahl der Speicherplätze in einerSpeichervorrichtung defekt sein. Ein defekter Speicherplatz kannunlesbar oder unzuverlässigsein, wobei er unterschiedliche Werte erzeugt, wenn er nacheinanderohne einen dazwischenliegenden Schreibvorgang gelesen wird. Derartigedefekte Speicherplätzekönnenbei einem anfänglichenTesten im Anschluß andie Herstellung identifiziert werden oder können über die Lebensdauer der Speichervorrichtunghinweg oder überein inkrementales Testen der Speichervorrichtung oder anhand andererMittel dynamisch identifiziert werden.
    [0004] 1 zeigt eine Veranschaulichungeines dreidimensionalen Speichers. Der Speicher weist neun Ebenen 101–109 auf,wobei jede Ebene ein gitterartiges Array aus Speicherplätzen, z.B.Speicherplatz 110, aufweist. Bei der in 1 gezeigten dreidimensionalen Speichervorrichtungsind die Speicherplätzeauf jeder Ebene wie die Zellen in einem mathematischen Array indexiert,wobei mit dem Speicherplatz (0, 0) begonnen wird und Zeile um Zeilebis zu dem Speicherplatz (31, 5) weitergegangen wird. Die Ebenensind durch einen dritten Index indexiert, so daß jeder Speicherplatz beispielsweisedurch Koordinaten (x, y, z) spezifiziert ist, wobei x der Indexeiner Zeile in einer Ebene ist, y der Index einer Spalte in einerEbene ist und z der Index einer Ebene in dem Stapel von Ebenen ist,der den dreidimensionalen Speicher bildet. Bei 1 sind eine Anzahl von Speicherplätzen bzw.Wörtern,wie z.B. der Speicherplatz 112, schattiert gezeigt, umanzugeben, daß der Speicherplatzdefekt ist.
    [0005] 2 veranschaulicht eine vonzahlreichen möglichenTechniken zum Adressieren von nicht-defekten Speicherplätzen ineinem Speicher, der defekte Speicherplätze umfaßt, wie beispielsweise demin 1 gezeigten. Wiein 2 gezeigt ist, kanneine Bittabelle 201 aufgebaut sein, um die Struktur derphysischen Speicherplätzein dem Speicher widerzuspiegeln. Wie in 2 gezeigt ist, umfaßt die Bittabelle 201 beispielsweise einArray aus Bits, z.B. Array 203, das jeder Ebene des in 1 gezeigten dreidimensionalenSpeichers entspricht. Bei jedem Bitarray umfaßt eine Zelle, z.B. Zelle 205,ein einzelnes Bit, das angibt, ob der entsprechende Speicherplatznicht-defekt oder defekt ist. Bei dieser Figur und in der folgendenErörterunggibt der Bitwert „0" einen nicht-defektenphysischen Speicherplatz an, und der Bitwert „1" gibt einen defekten physischen Speicherplatzan. Man beachte, daß dasBitarray 203 in 2 ähnlich demIndexieren der Speicherplätzein der entsprechenden dreidimensionalen Speicherebene 101 indem in 1 gezeigten Speicherindexiert ist. Die Entsprechung zwischen den defekten Bits, diein 1 als schattierteZellen gezeigt sind, und Zellen in dem Bitarray 203, dieden Bitwert „1" enthalten, ist ohneweiteres ersichtlich.
    [0006] Wenneine Defekte-Speicherplätze-Tabelle,z.B. die Bittabelle 201 in 2,hergestellt ist, könnendie nicht-defektenSpeicherplätzein einer monoton ansteigenden Reihenfolge sequenziert werden, indemdiejenigen Speicherplätze,die in der Bittabelle als defekt verifiziert werden, ignoriert werden.Mit anderen Worten kann eine Sequenz von logischen, nicht-defektenSpeicherplätzenerstellt werden, so daß physischeSpeicherplätzeunter Verwendung von logischen Speicherplätzen, die nicht-defekt sind,adressiert werden können.Eine Möglichkeit,dies zu tun, besteht darin, einen Index 207 der logischenSpeicherplatzadresse jedes der physischen Speicherplätze, dieden Bittabelleneinträgenin der ersten Zeile 209 des Bittabellenarrays entsprechen, zuerstellen. Man kann fürjedes Bitarray, das einer Ebene in dem Speicher entspricht, einenseparaten In dex, z.B. Index 207, erstellen. Der Index kannverwendet werden, um einen Speicherplatz zu finden, der sich inder Näheeines gewünschtenSpeicherplatzes befindet und demselben vorausgeht, und anschließend kanndie entsprechende Spalte des Bitarrays überquert werden, um die exaktephysische Adresse des Speicherplatzes in dem Speicher zu finden.Wenn man beispielsweise den physischen Speicherplatz mit der logischenSpeicherplatzadresse 100 finden möchte, könnte man den Index 207 durchsuchen,um die Zelle 212 zu lokalisieren, die die logische Speicherplatzadresse „98" enthält. DerIndex in dieser Zelle ist der Index der Spalte in dem Bitarray,das eine erste Zelle aufweist, die der logischen Speicherplatzadresseentspricht. Somit entspricht die Zelle 214 in dem Bitarray203 einem Speicherplatz, der die logische Speicherplatzadresse „98" aufweist. Anschließend kanndie Spalte Zelle um Zelle nach unten überquert werden, um die Bitarrayzelle 216, dieder logischen Speicherplatzadresse „100" entspricht, zu lokalisieren. Während der Überquerungwerden jegliche Bitarrayzellen, die den Bitwert „1" enthalten, übersprungen. Man beachte, daß der Unterschiedzwischen dem Inhalt aufeinanderfolgender Zellen in dem Index 207 nichtkonstant ist. Falls in der Spalte einer Ebene des Speichers, dieeiner Spalte des Bitarrays entspricht, keine defekten Speicherplätze vorliegen,wird die nächsteZelle in dem Index um die Anzahl von Zellen in einer Spalte desBitarrays inkrementiert. Beispielsweise gibt der Wert „6" in der zweiten Zelle 218 desIndex 207 an, daß inder ersten Spalte der ersten Ebene des Speichers keine defektenSpeicherplätzeauftreten. Wegen des Auftretens eines defekten Speicherplatzes inder zweiten Spalte der ersten Ebene des Speichers (114 in 1), der durch den Bitwert „1" in der Zelle 220 desBitarrays 203 identifiziert ist, ist jedoch der Wert inder dritten Zelle des Index 207 222 „11", nur fünf größer alsder vorhergehende Wert.
    [0007] DerIndex und die Speicherplatzbittabelle (bei 2 207 bzw. 201) stelleneines von vielen unterschiedlichen mögli chen Verfahren zum sequentiellenIndexieren der nicht-defektenSpeicherplätzein einem Speicher dar. Den meisten Verfahren gemeinsam ist eineBittabelle, beispielsweise Bittabelle 201 in 2, bei der die nicht-defektenund die defekten Speicherplätzein dem Speicher identifiziert werden. Diese Bittabelle muß in einemSpeicher mit einer sehr hohen Geschwindigkeit gespeichert werden,um ein effizientes Adressieren eines Speichers bei hoher Geschwindigkeitzu ermöglichen,da möglicherweisejedesmal, wenn auf einen Speicherplatz zugegriffen wird, auf dieBittabelle zugegriffen werden muß. Derartige Hochgeschwindigkeitsspeichersind jedoch viel teurer als üblicherweiseverwendete Speicher einer geringeren Geschwindigkeit. Beispielsweisewird auf Hochgeschwindigkeitsregister in einem Prozessor allgemeinviel schneller zugegriffen, sie sind jedoch viele Größenordnungenteurer als die dynamischen Direktzugriffsspeicher einer geringerenGeschwindigkeit, die allgemein übereinen oder mehrere Speicherbusse mit dem Prozessor verbunden sind.Obwohl ein schnellerer Betrieb erhalten werden kann, indem einegrößere Anzahlvon Registern in einen Prozessor aufgenommen wird, wird der Prozessormit jedem hinzugefügtenRegister immer teurer. Aus diesen Gründen erkannten Hersteller undEntwerfer von Speichern und Hersteller und Benutzer von Vorrichtungen,die diese Speicher enthalten, ein Verfahren zum effizienten Speichernvon Speicherplatzbittabellen wie z.B. der Speicherplatzbittabelle 201,die in 2 gezeigt ist.
    [0008] DieAufgabe der vorliegenden Erfindung besteht darin, Verfahren undeinen Speicher zu schaffen, die die Länge einer Defektliste für eine Speichervorrichtungminimieren.
    [0009] DieseAufgabe wird durch Verfahren gemäß Anspruch1 oder 14 sowie durch einen Speicher gemäß Anspruch 16 gelöst.
    [0010] Beieinem allgemeinen Verfahren, das einen Satz von Ausführungsbeispielender vorliegenden Erfindung darstellt, wird eine Defekte-Speicherplätze-Bittabelleunter Verwendung ei nes Verfahrens einer verlustbehafteten Komprimierung/Entkomprimierungkomprimiert. Ein Verfahren einer verlustbehafteten Komprimierung/Entkomprimierungkann komprimierte Informationen auf eine Entkomprimierung hin verändern, kannjedoch zu einer stärkerenKomprimierung führen.Ein bestimmtes Ausführungsbeispielder vorliegenden Erfindung verwendet eine Vektorquantisierungstechnik,um eine Defekte-Speicherplätze-Bittabelle,die defekte Speicherplätzein einem Speicher identifiziert, zu komprimieren. Das Vektorquantisierungsverfahrenverwendet eine iterative Partitionierung eines Vektorraums. EinePartitionierung verwendet eine Boolesche ODER-Metrik zum Bestimmender Affinitätenvon Vektoren fürjedes Codewort, das als der anfänglicheVektor fürjede entstehende Partition ausgewählt wird. Der spezielle Vektor(1,1...1) wird überalle Iterationen hinweg als Codewort in dem Codebuch unterhalten.Das Vektorquantisierungsverfahren ist entworfen, um eine asymmetrischeVerzerrung zu erzeugen, so daß eindefekter Speicherplatz nicht durch eine Komprimierung und Entkomprimierungverzerrt wird, um unkorrekterweise anzugeben, daß der Speicherplatz fehlerfreisei. Lediglich Verzerrungen, die fehlerfreie Speicherplätze aufDefekte-Speicherplätze-Angaben in der Defekte-Speicherplätze-Bittabellerelegieren, sind erlaubt, was zu einem Verlust von Speicherplätzen führt, wasjedoch verhindert, daß mansich auf einen defekten Speicherplatz verläßt. Da diverse unterschiedlicheKomprimierungs-/Entkomprimierungsverfahren für unterschiedliche Typen vonDefektverteilungen innerhalb eines Speichers geeignet sein können, istein Verfahren vorgesehen, um aus einer Anzahl von Komprimierungs-/Entkomprimierungsverfahrendas füreine bestimmte Defektwahrscheinlichkeitsverteilung am besten geeigneteKomprimierungs-/Entkomprimierungsverfahren auszuwählen. EinLauflängenquantisierungsverfahrenkann ebenfalls verwendet werden, um eine Defekte-Speicherplätze-Bittabelle zu komprimieren.
    [0011] BevorzugteAusführungsbeispieleder vorliegenden Erfindung werden nachfolgend Bezug nehmend aufdie beiliegenden Zeichnungen nähererläutert.Es zeigen:
    [0012] 1 eine Veranschaulichungeines dreidimensionalen Speichers;
    [0013] 2 eine von zahlreichen möglichenTechniken zum Adressieren nicht-defekter Speicherplätze innerhalbeines Speichers, der defekte Speicherplätze umfaßt, wie z.B. der in 1 gezeigte;
    [0014] 3A–3C dieLauflängencodierungstechnik;
    [0015] 4-9 ein Vektorquantisierungsverfahren zumKomprimieren von Defekte-Speicherplätze-Bittabellen, das ein Ausführungsbeispielder vorliegenden Erfindung darstellt;
    [0016] 10 ein Ablaufsteuerungsdiagrammder LBG-Technik fürdie Erstellung eines Codebuchs;
    [0017] 11 ein Ablaufsteuerungsdiagrammeines LBG-Algorithmuseines Asymmetrische-Verzerrung-Modells,der verwendet werden kann, um ein Codebuch für eine Vektorquantisierungs-Defekte-Speicherplätze-Tabelle-Komprimierungund -Entkomprimierung bei einem Ausführungsbeispiel der vorliegendenErfindung zu erstellen;
    [0018] 12 und 13 das Lauflängenquantisierungskomprimierungs-/Entkomprimierungsverfahren,das ein Ausführungsbeispielder vorliegenden Erfindung darstellt; und
    [0019] 14 und 15 in einem Format eines Ablaufsteuerungsdiagrammseine Übersicht über einVerfahren zum Bereitstellen eines Speichers, das eines der be schriebenenAusführungsbeispieleder vorliegenden Erfindung beinhaltet.
    [0020] Umeine Bittabelle, die defekte Speicherplätze in einem Speicher darstellt,so kompakt wie möglichin einem Hochgeschwindigkeitsspeicher zu speichern, um die zum Implementierendes Speichers notwendige Menge an Hochgeschwindigkeitsspeicher zuminimieren, komprimieren eine Anzahl von Ausführungsbeispielen der vorliegendenErfindung die Defekte-Speicherplätze-Tabelle,die angibt, welche physischen Speicherplätze defekt sind, und speicherndie Defekte-Speicherplätze-Tabellein einem Hochgeschwindigkeitsspeicher. Wie oben erläutert wurde,sind die Defekte-Speicherplätze-Tabellen üblicherweiseBittabellen, bei denen der Bitwert „0" verwendet wird, um nicht-defekte Speicherplätze anzugeben,währendder Bitwert „1" verwendet wird,um defekte Speicherplätzezu bezeichnen. Selbstverständlichkann auch eine umgekehrte Konvention verwendet werden.
    [0021] Esgibt viele verschiedene Typen von Komprimierungstechniken. DieseTypen fallen in zwei allgemeine Kategorien: (1) verlustfreie Komprimierungstechniken,die eine exakte Rekonstruktion einer komprimierten Bittabelle ermöglichen;und (2) verlustbehaftete Komprimierungstechniken, die allgemeinVerzerrungen bezüglichder ursprünglichcodierten Bittabelle auf eine Entkomprimierung hin erzeugen. Einehinreichend bekannte verlustfreie Komprimierungstechnik ist als „Lauflängencodieren" bekannt. 3A–3C veranschaulichendie Lauflängencodierungstechnik.Man beachte, daß ungeachtetder Struktur eines Speichers alle Speicherplätze in einem Speicher sequentiellgeordnet werden können,so daß dieBittabelle, die angibt, welche der Speicherplätze defekt sind, ebenfallssequentiell sein kann. Bei 3A isteine kurze Defekte-Speicherplätze-Bittabelle 302 zusammenmit einer komprimierten Version der Bittabelle 304 gezeigt.Diese Komprimierung ist bei dem in 3A gezeigtenBeispiel nicht sehr dramatisch, da die komprimierte Bitta belle 304 nurum drei Bits kürzerist als die unkomprimierte Bittabelle 302, die als dieEndleerbits 305–307 in 3A gezeigt sind. Die Bittabelle 302 wird über einLauflängencodierencodiert oder komprimiert. Bei dieser Technik werden Zeichenfolgenvon sequentiellen Null-Bits und Zeichenfolgen von sequentiellenEins-Bits durch eine Längeder Zeichenfolge dargestellt, auf die der Bitwert der Bits in derZeichenfolge folgt. Beispielsweise umfaßt die Bittabelle 302 eineführendeZeichenfolge von 14 Null-Bits 310. Diese Zeichenfolge von14 Null-Bits wird bei der komprimierten Version der Bittabelle 304 alseine Vier-Bit-Ganzzahl 312 dargestellt,die den Wert „14" darstellt, auf dieein Ein-Bit-Wert „0" 314 folgt, was angibt,daß dieBits in der 14-Bit-Zeichenfolge Null-Bits sind. Desgleichen wirddie nächsteZeichenfolge von drei Eins-Bits 316 in der unkomprimiertenBittabelle 302 in der komprimierten Bittabelle durch dieVier-Bit-Ganzzahl 318 dargestellt, die den Wert „3" darstellt, auf dieein Ein-Bit 320 folgt, das den Bitwert „1" aufweist, was angibt, daß die Zeichenfolgevon drei Bits Bitwerte von „1" aufweist. Ein Lauflängencodierenist eine verlustfreie Codierungstechnik, da die ursprünglicheBittabelle 302 aus der komprimierten Version der Bittabelle 304 exaktrekonstruiert werden kann. Jede Teilzeichenfolge der unkomprimiertenBittabelle kann in einer Reihenfolge aus der komprimierten Bittabelleerzeugt werden, wobei bei der komprimierten Version der Bittabellebei der Darstellung der äußerstenlinken Teilzeichenfolge begonnen wird. Wie in 3B gezeigt ist, werden bedeutend größere Komprimierungsverhältnisseerhalten, wenn lediglich relativ wenige Speicherplätze defektsind. Bei dem in 3B gezeigtenBeispiel wird eine fast 50 Prozent betragende Komprimierung erzielt.Wenn größere Lauflängenganzzahlenverwendet werden, beispielsweise 32-Bit-Ganzzahlen, und das Auftretenvon Defekten ziemlich selten ist, können sogar noch größere Komprimierungsverhältnisseerzielt werden. Wie jedoch in 3C gezeigtist, erzeugen verlustfreie Komprimierungstechniken eventuell nichtimmer eine Komprimierung, sondern können bezüglich bestimmter Eingangsbittabel lenkomprimierte Bittabellen erzeugen, die größere Längen aufweisen als die ursprünglicheunkomprimierte Bittabelle. Mit anderen Worten können verlustfreie Komprimierungstechnikenbei bestimmten Typen von Defektverteilungen auf spektakuläre Weiseversagen. Bei 3C bestehtein relativ hoher Anteil an defekten Speicherplätzen, und die defekten Speicherplätze sindmit nicht-defekten Speicherplätzendurchsetzt. In diesem Fall erzeugt eine Lauflängenkomprimierung lediglichder ersten sechs Bits 328 der unkomprimierten Bittabelle 330 28Bits einer lauflängencodiertenBittabelle in der komprimierten Version der Bittabelle 332.Somit führtein Lauflängencodierenin diesem Fall zu einer Datenerweiterung statt zu einer Datenkomprimierung.Alternativ dazu kann eine Lauflängencodierungstechnikeiner variablen Längestatt einer feststehenden Längeverwendet werden. Bei einer Variable-Länge-Codierungstechnik kannein präfixfreierCode verwendet werden, um die Lauflängenwerte zu Sequenzen vonVariable-Länge-Bitzeichenfolgenzu codieren. Die Größen, inBits, von Lauflängencodierungenspiegeln allgemein die Auftretenshäufigkeit der Codierungen wider,so daß dieam häufigstenauftretenden Lauflängenam exaktesten codiert werden. Es können diverse unterschiedlicheArten von Variable-Länge-Lauflängencodierungenverwendet werden, um die Codierung an ein statistisches Modell derzu komprimierenden Daten anzupassen, um die Daten so effizient wiemöglichzu komprimieren.
    [0022] EinAusführungsbeispielder vorliegenden Erfindung beinhaltet die Verwendung einer Vektorquantisierung,um eine Defekte-Speicherplätze-Bittabellezu komprimieren. Vektorquantisierung ist eine verlustbehaftete Komprimierungstechnik.Es wärenicht naheliegend, eine verlustbehaftete Komprimierungstechnik zum Komprimierenvon Speicherplatz-Defekt-Bittabellenzu verwenden, da die ursprünglicheDefekte-Speicherplätze-Bittabelleauf eine Entkomprimierung hin verzerrt sein kann, was bedeutet,daß Bits,die in der ursprünglichenBittabelle Bitwerte „0" aufweisen, so verzerrtsein können,daß siebei der entkomprimierten Version Bitwerte „1" aufweisen, und daß Bits, die Bitwerte „1" aufweisen, so verzerrtsein können,daß siebei der entkomprimierten Version der Defekte-Speicherplätze-BittabelleBitwerte „0" aufweisen. In demerstgenannten Fall wird ein nicht-defekter Speicherplatz als defektangesehen, was eine Verschwendung an nicht-defektem Speicherplatzin dem Speicher darstellt. In dem letztgenannten Fall wird ein erkannterdefekter Speicherplatz als nicht-defekt angesehen, was zu Fehlernverschiedener Schwere, einschließlich katastrophischer Fehler,führenkann. Somit könntenverlustbehaftete Komprimierungstechniken sinnvollerweise als inakzeptabelangesehen werden. Jedoch diente die Anerkennung, daß eine Komprimierungs-/Entkomprimierungstechnik,die eine asymmetrische Verzerrung erzeugt, zum Komprimieren vonDefekte-Speicherplätze-Bittabellenakzeptabel sein kann, als Motivation für das erste Ausführungsbeispielder vorliegenden Erfindung.
    [0023] 4-9 veranschaulichen ein Vektorquantisierungsverfahrenzum Komprimieren von Defekte-Speicherplätze-Bittabellen, das ein Ausführungsbeispielder vorliegenden Erfindung darstellt. Wie in 4 gezeigt ist, kann eine Defekte-Speicherplätze-Bittabelle 402 ineine Sequenz von Bitvektoren 404–407 unterteilt sein. Mitanderen Worten kann die Defekte-Speicherplätze-Bittabelle 402 alseine Sequenz von Vier-Bit-Bitvektoren betrachtet werden, wie in 4 gezeigt ist. Vektorquantisierungist ein Prozeß zumKomprimieren jedes der sequentiellen Vektoren zu einem Index. EineEntkomprimierung einer übereine Vektorquantisierung komprimierten Bittabelle beinhaltet einZurücktransformiereneiner Sequenz von Indizes zu Bitvektoren.
    [0024] 5 veranschaulicht die Transformationeines Bitvektors zu einem Indexvektor über eine Vektorquantisierungund eine anschließendeRekonstruktion des Bitvektors. Wie in 5 gezeigtist, wird ein Bitvektor 502, der einen der sequentiellenBitvektoren in einer Eingangsbittabelle darstellt, durch einen Codierer 504 ineinen Indexvektor 506 transfor miert. Der Indexvektor istkürzerals der Bitvektor, wodurch ein Komprimierungsverhältnis derEingangsbittabelle erzeugt wird, das gleich dem Verhältnis derLänge desBitvektors zu der Längedes Indexvektors ist. Der Indexvektor 506 ist der Indexeines Codeworts in einem Codebuch, das nachfolgend beschrieben wird.Eine Rekonstruktion einer Bittabelle aus einer Sequenz von Indexvektorenbeinhaltet ein Leiten der Indexvektoren durch einen Decodierer 508,um einen entsprechenden Vektor 510 zu erzeugen. Der Decodiererverwendet den Index, um das entsprechende Codewort zu lokalisieren,und erzeugt das Codewort als den Ausgangsbitvektor.
    [0025] 6 zeigt einen beispielhaftenBitvektorraum und einen entsprechenden Indexvektorraum. Wie in 6 gezeigt ist, können, wennVier-Bit-Eingangsvektoren verwendet werden, 16 unterschiedlichemögliche Eingangsvektoren 602 durcheinen Vektorquantisierungscodierer empfangen werden. Falls der Codiererein Codebuch verwendet, das vier Codewörter enthält, so werden vier unterschiedlicheIndizes benötigt,um das Codebuch zu indexieren. Somit können Zwei-Bit-Indexvektoren verwendetwerden, um die vier Codewörterin dem Codebuch zu indexieren. Wie in 6 gezeigtist, werden somit Vier-Bit-Bitvektoren durch eine Vektorquantisierungscodierungzu Zwei-Bit-Indexvektoren 604 transformiert.
    [0026] Wiebeim LauflängencodierenkönnenVektorquantisierungstechniken unter Verwendung eines verlustfreien,präfixfreienVariable-Länge-CodesIndex zu binärenZeichenfolgen codieren. Dadurch können die Codewörter, aufdie am häufigstenBezug genommen wird, mit größerer Exaktheitindexiert werden, während Codewörter, aufdie weniger häufigBezug genommen wird, mit längerenIndizes indexiert werden können. Wenneine nicht-konstante Bezugnahmehäufigkeitsverteilungvorliegt, kann unter Verwendung von Indizes einer variablen Länge einegrößere Codierungseffizienzerhalten werden.
    [0027] Wieoben erwähntwurde, muß einasymmetrisches Vektorquantisierungsverfahren für ein Komprimieren von Defekte-Speicherplätze-Bittabellenausgelegt sein. 7 zeigteine Tabelle, die die verschiedenen Codewörter veranschaulicht, die verwendetwerden könnten,um jeden der 16 unterschiedlichen möglichen Vier-Bit-Eingangsvektorendarzustellen. Die 16 unterschiedlichen möglichen Vier-Bit-Eingangsvektorensind als Markierungen 702 von 16 Spalten, z.B. Spalte 704,in der Tabelle 700 der 7 gezeigt.Die Vier-Bit-Werte in jeder Spalte stellen die möglichen unterschiedlichen Codewörter dar,die dem jeweiligen Vier-Bit-Eingangsvektor,der die Spalte kennzeichnet, entsprechen können. Beispielsweise kann derEingangsvektor „0100" 706 durchjegliche der Codewörter „0100", „0101", „0110", „0111", „1100", „1101", „1110", und „1111" dargestellt werden.Kein anderes Codewort ist möglich,da ein Codewort fürden Vier-Bit-Bitvektor „0100" in keiner der Bitpositionen,in denen der Eingangsvektor einen Bitwert „1" aufweist, einen Bitwert „ 0" enthalten kann.Mit anderen Worten wird eine Angabe eines defekten Speicherplatzeseventuell nicht zu einer Angabe eines nicht-defekten Speicherplatzesverzerrt. Man beachte, daß daseinzige fürden Eingangsvektor „1111" 708 mögliche Codewort dasCodewort „1111" ist, und man beachteferner, daß für den Eingangsvektor „0000" jegliches Codewortverwendet werden kann. Da das einzige für den Eingangsvektor „1111" mögliche Codewortdas Codewort „1111" ist, muß sich dasCodewort „1111" in jedem möglichenCodebuch befinden, um eine unerwünschteVerzerrung zu verhindern.
    [0028] 8 stellt ein möglichesVektorquantisierungsschema fürVier-Bit-Eingangsvektoren und Zwei-Bit-Indexvektoren, die ein Codebuch,das vier Codewörterenthält,indexieren, dar. Das großeRechteck 802 in 8 zeigtalle möglichenunterschiedlichen Eingangsvektoren. Die möglichen Eingangsvektoren sindbei 8 in vier Gruppen 804–807 partitioniertbzw. unterteilt. Die erste Gruppe bzw. Partition 804 umfaßt lediglichden Eingangsbitvektor „0000". Die zweite Partition 805 umfaßt die Eingangsbitvektoren „0001", „0010" und „0011". Die dritte Partition 806 umfaßt die Bitvektoren „0100", „1000" und „1100". Die vierte Partition 802 umfaßt die verbleibendenmöglichenEingangsvektoren. Der eingekreiste Vektor in jeder Partition, z.B.der eingekreiste Vektor 810, ist das Codewort für die Partition.Es liegen vier Codewörter 810–813 für die vierPartitionen vor. Die vier Codewörterwerden in der Größenordnungder Codewörter,wenn sie als 4-Bit-Ganzzahlen betrachtet werden, indexiert. Somitkomprimiert eine Vektorquantisierungskomprimierungstechnik, diedas Schema der 8 verwendet,den Eingangsvektor „0000" der Partition 804 zudem Indexvektor „00", der den Index für das Codewort 811 für die Partitiondarstellt. Desgleichen würdeder Eingangsvektor „1010" 814 zudem Indexvektor „11" komprimiert, derdas Codewort fürdie Partition „1111" 810 indexiert.
    [0029] 9 veranschaulicht eine Komprimierungeiner beispielhaften Bittabelle anhand eines Vektorquantisierungskomprimierungsschemasunter Verwendung der in 8 gezeigtenPartitionierung. Die Eingangsbittabelle 902 ist in Vier-Bit-Vektoren, beispielsweiseden Vier-Bit-Vektor 904, partitioniert. Jeder Eingangsvektor wirdanschließendin einen Zwei-Bit-Indexvektor, z.B. den Zwei-Bit-Indexvektor 906,transformiert, indem der Zwei-Bit-Index verwendet wird, der demCodewort in der Partition entspricht, der der Eingangsvektor gemäß dem Schemader 8 zugewiesen ist.Allgemein wird der einem Eingangsvektor entsprechende Index unter Verwendungeiner Entfernungs- oder Verzerrungsmetrik berechnet, obwohl alternativIndizes fürjeden Eingangsvektor gespeichert werden können. In 9 ist ferner eine entkomprimierte Bittabelle 908 gezeigt,die von der komprimierten Bittabelle 906 entkomprimiertwurde. Eine Entkomprimierung wird durchgeführt, indem jeder Indexvektordurch das Codewort, das er indexiert, ersetzt wird. In bestimmtenFällenerzeugt eine Entkomprimierung genau denselben Bitvektor, wie erursprünglichin der unkomprimierten Bittabelle vorlag. Beispielsweise entkomprimiertder Bitvektor „0000" 904 zudem identischen Vier-Bit-Vektor „0000" 910 in der entkomprimiertenBittabelle. Andere Vektoren entkomprimieren jedoch nicht gerade.Beispielsweise entkomprimiert der zweite Bitvektor 912 inder unkomprimierten Bittabelle 902 zu einem unterschiedlichenBitvektor 914. Es stellt sich heraus, daß sich dieBits 916-920 durch eine Entkomprimierung von dem Bitwert „0" zu dem Bitwert „1" verändert habenund somit eine Verzerrung darstellen.
    [0030] Derbei dem beschriebenen Ausführungsbeispielder vorliegenden Erfindung verwendete Vektorquantisierungsansatzist so entworfen, daß erbezüglicheiner Verzerrung asymmetrisch ist, so daß sich der Wert „0" gelegentlich zu „1" verändern kann,so daß sichjedoch der Wert „1" infolge einer Komprimierungs-/Entkomprimierungsverzerrungnicht zu „0" ändern kann. Folglich können nicht-defekteSpeicherplätzefälschlicherweiseals defekte Speicherplätzecharakterisiert werden, defekte Speicherplätze werden jedoch nicht fälschlicherweiseals nicht-defekte Speicherplätzecharakterisiert. Ein Asymmetrische-Verzerrung-Maß wird für eine Vektorquantisierungvon Defekte-Speicherplätze-Tabellen verwendet,wobei die Verzerrung eines binärenWerts x und die entkomprimierte Form des binären Werts z durch folgendesgegeben sind:
    [0031] DieEffizienz und Effektivitätder Vektorquantisierung zum Komprimieren und Entkomprimieren einer Defekte-Speicherplätze-Tabelle,die oben unter Bezugnahme auf 4-9 beschrieben wurde, hängt voneiner ordnungsgemäßen Erstellungdes Codebuchs von Codewörternab. Ein Satz von Trainingsvektoren, die auch als Eingangsvektorenbezeichnet werden, wird üblicherweisebei der Codebucherstellung verwendet, so daß die Auftretenswahrscheinlichkeitenverschiedener Vektoren beim Erstellen eines effizienten Codierensvon Vektoren, deren Auftreten wahrscheinlich ist, berücksichtigtwerden. Die Codewörtermüssennatürlichden Vek torraum von Trainingsvektoren auf eine Weise partitionieren,die eine Verzerrung minimiert. Je größer die Anzahl von Codewörtern, destogrößer dieAnzahl von Indizes, die notwendig sind, um das Codebuch zu indexieren.Deshalb hängtdie Komprimierungsrate von der Codebuchgröße ab; wenn jedoch eine optimalePartitionierung füreinen gegebenen Satz von Eingangsdaten gegeben ist, erhöht sichdie Verzerrungsrate allgemein mit der Verringerung der Codebuchgröße.
    [0032] Esgibt eine Anzahl unterschiedlicher Lösungsansätze bezüglich eines Erstellens einesCodebuchs für eineVektorquantisierungskomprimierung/-entkomprimierung. Eine beliebteTechnik wird als „LBG-Algorithmus" oder einfach „LBG" bezeichnet, wobeiauf die Autoren des Algorithmus, Linde, Buzo und Gray, Bezug genommenwird. 10 ist ein Ablaufsteuerungsdiagrammder LBG-Technik füreine Erstellung eines Codebuchs. Bei Schritt 1002 werdeneine Codebuchgröße, N, eineCodewortvektorabmessung, n und ein Schwellengrenzparameter s ausgewählt. DieCodebuchgröße N istdie Anzahl von Codewörtern,und der Schwellengrenzparameter s ist eine Schwelle für eine relative Änderungder Verzerrung zwischen Codebüchern,die durch aufeinanderfolgende Iterationen des LBG erzeugt werden,unter der der Algorithmus mit dem derzeit erstellten Codebuch endet.Von dem aktuellen Codebuch nimmt man bei seiner Beendigung an, daß es einem lokalenoptimalen Codebuch zumindest nahekommt. Verschiedene Kriterien können verwendetwerden, um die Codebuchgröße N unddie Codewortvektorabmessung n auszuwählen. Wie oben erläutert wurde,ist das Komprimierungsverhältnis,das durch ein Verwenden des Codebuchs bei der Vektorquantisierungerreichbar ist, direkt auf die Codebuchgröße N bezogen. Die Effizienzeiner Auswahl eines nahezu optimalen Codebuchs wird ermöglicht,indem die Codewortvektorabmessung n groß gewählt wird, was eine größere Vielfaltbei der Vektorraumpartitionierung liefert. Wenn die Codewortvektorabmessungn jedoch zu groß gewählt wird,kann es praktisch unmöglichwerden, iterativ zu einem lokal optimalen Code buch zu gelangen,geschweige denn, das optimale Codebuch zu finden.
    [0033] BeiSchritt 1004 wird die Iterationsvariable k auf 1 eingestellt.Die Iterationsvariable k verfolgt die Anzahl von Malen, die eineInnenschleife des LBG-Algorithmus ausgeführt wird. Bei Schritt 1006 wählt der LBG-Algorithmusdann einen anfänglichenSatz von N n-dimensionalen Vektoren J als anfängliches Codebuch. Die Auswahldes anfänglichenCodebuchs kann auf diverse verschiedene Weisen erfolgen. Ein Lösungsansatzbesteht darin, einen zufälligerzeugten Satz von Vektoren zu verwenden. Bei einem Zufallserzeugungsansatzwird der Index einer Partition als Keim für einen Pseudozufallszahlengeneratorverwendet, der entsprechend dimensionierte und entsprechend verteiltePseudozufallsvektoren erzeugt. Ein Vorteil dieses Lösungsansatzesbesteht darin, daß dieCodewörternicht gespeichert werden müssen.Statt dessen könnendie aus einer komprimierten Tabelle extrahierten Indizes als Keimein denselben Pseudozufallszahlengenerator eingegeben werden, umdie entsprechenden Codewörterwiederzugewinnen. Ein weiterer Lösungsansatzbesteht darin, jeden Eingangsvektor in seine eigene Partition zuplazieren und anschließendPartitionen, die nahe beieinander liegen, paarweise zu verschmelzen,bis eine annehmbar kleine Anzahl von Partitionen erzeugt wird, wobeider Schwerpunktvektor jeder Partition als Codewort verwendet wird.Ein Maß für Nähe kannauf einer Summe von euklidischen Abständen oder auf alternativenAbstandsmaßenberuhen. Ein dritter Lösungsansatzbesteht darin, einen Schwerpunkt für den Eingangsvektorraum zuberechnen, den Schwerpunkt fürein erstes Codewort zu verwenden und diesen Schwerpunkt anschließend systematischzu stören,um die verbleibenden Codewörterfür dasanfänglicheCodebuch zu erzeugen.
    [0034] DieSchritte 1008–1013 bildenzusammen eine iterative Schleife, bei der die anfänglich gewählten Codewörter modifiziertwerden, bis ein akzeptables Verzerrungsniveau er halten wird. Wennder Unterschied zwischen der berechneten Verzerrung für das beider vorherigen Iteration erstellte Codebuch und der für das aktuelleCodebuch berechneten Verzerrung unter der Schwelle s liegt, so endetder LBG-Algorithmus,und das aktuelle Codebuch Q wird bei Schritt 1014 zurückgegeben.Das Codebuch besteht aus N Partitionen von Eingangsvektoren, Qi, wobei i zwischen 0 und N – 1 liegt,einschließlicheines Codeworts J(i)in jeder Partition Qi. Bei Schritt 1008 werden Eingangsvektoren,die näheran jedem Codewort J(i) als an jeglichemanderen Codewort liegen, als Angehörige der Partition i ausgewählt, diedas Codewort J(i) umfaßt, gemäß Qi = {Xn|d(Xn, Jn ( i)) < d(Xn,Jn (j)) ∀ j ≠ i}wobeibeispielsweise i und j∊{0, 1, ... N – 1} und wobei beispielsweise
    [0035] Mitanderen Worten werden bei Schritt 1008 Eingangsvektorenin N Partitionen partitioniert. Man beachte, daß die Verzerrung d alternativso definiert sein kann, daß sieein weiteres, eine Verzerrung widerspiegelndes Maß und nichtein euklidischer Abstand ist. Bei Schritt 1009 wird für das aktuelleCodebuch Q, das bei der kten Iteration des Schrittes 1008 erstelltwird, eine Gesamtverzerrung D(k) berechnet.Die Gesamtverzerrung wird als folgendes berechnet:
    [0036] BeiSchritt 1010 bestimmt der LBG-Algorithmus, ob k größer als1 ist oder nicht. Falls dies der Fall ist, so wurde zu vor ein D(k– 1) berechnet, und die relative Verzerrungsänderung
    [0037] Dierelative Verzerrungsänderung
    [0038] DerLBG-Algorithmus muß aufeine Verwendung bei einem Vektorquantisierungsschema zum Komprimiereneiner Defekte-Speicherplätze-Tabellezugeschnitten sein. 11 istein Ablaufsteuerungsdiagramm eines LBG-Algorithmus eines Asymmetrische-Verzerrung-Modells,der bei einem Ausführungsbeispielder vorliegenden Erfindung verwendet werden kann, um ein Codebuchfür eineVektorquantisierungs-Defekte-Speicherplätze-Tabelle-Komprimierungund -Entkomprimierung zu erstellen. Viele Schritte bei dem LBG-Algorithmusdes Asymmetrische-Verzerrung-Modells sind ähnlich denjenigen in dem LBG-Algorithmus,der unter Bezugnahme auf 10 beschriebenwurde, und werden nicht erneut erläutert. Statt dessen werdenlediglich die Unterschiede erläutert.Der erste Unterschied findet sich bei Schritt 1106. EinVergleich des Schritts 1106 und des Schritts 1006 in 10 zeigt, daß der anfänglicheSatz von Vektoren J bei dem LBG-Algorithmusdes Asymmetrische-Verzerrung-Modells einen Vektor umfassen muß, der denWert „1" in jeder Positionin dem Vektor aufweist. Dieser Vektor muß vorliegen, um zu gewährleisten,daß aufeine Entkomprimierung hin kein „1"-Wert zu einem „0"-Wert verzerrt wird und dadurch einenidentifizierten defekten Speicherplatz dahingehend ändert, daß in derDefekte-Speicherplätze-Tabelleangegeben wird, daß derSpeicherplatz nicht defekt sei. Wie oben unter Bezugnahme auf 8 erläutert wurde, ist das einzigegeeignete Codewort füreinen Eingangsvektor, das aus „1"-Werten in allenPositionen besteht, das Codewort, das aus „1"-Werten in allen Positionen besteht,so daß dasCodewort in dem Codebuch vorhanden sein muß. Ein zweiter Unterschiedfindet sich bei Schritten 1108 und 1109, wennsie mit den entsprechenden Schritten 1008 und 1009 in 10 verglichen werden. Wieaus Schritt 1108 hervorgeht, verwendet der LBG-Algorithmusdes Asymmetrische-Verzerrung-Modells ein asymmetrisches Abstandsmaß, und nichtein euklidisches Abstandsmaß,das ein symmetrisches Verzerrungsmaß reflektiert:
    [0039] Eindritter Unterschied findet sich bei Schritt 1113 im Vergleich zuSchritt 1013 in 10.Wenn das Codebuch, das Vektoren J aufweist, modifiziert wird, muß der Vektormit dem Wert „1" in allen Positionenin dem modifizierten Codebuch enthalten sein. Falls die Modifikationferner ein Berechnen von Schwerpunkten oder andere abstandsbezogeneTechniken beinhaltet, muß dieoben beschriebene Asymmetrischer-Abstand-Metrik statt einer Euklidischer-Abstand-Metrik verwendetwerden. Bei dem LBG-Algorithmus des Asymmetrische-Verzerrung-Modellswerden Schwerpunkte als das logische ODER der Vektoren in der Partitionberechnet.
    [0040] Eineoptimale Größe für ein Codebuchkann durch eine Minimierung eines Maßes von gegenseitigen Informationenbestimmt werden, die aus der Wahrscheinlichkeitsverteilung pX von Eingangsvektoren x und der bedingtenWahrscheinlichkeitsverteilung
    [0041] Beieinem verlustbehafteten Codierer/Decodierer möchte man die gegenseitigenInformationen I(x ^; x) überdie bedingte Wahrscheinlichkeitsverteilung
    [0042] DurchMinimieren der gegenseitigen Informationen I(x ^; x) vorbehaltlichder Einschränkungbezüglich dermaximal zulässigenVerzerrung wird eine optimale Ratenverzerrungsrate R(δ) erhalten,wobei δ gleich demBruchteil von nicht-defekten Speicherplätzen ist, die aufgrund einerKomprimierungs-/Entkomprimierungsverzerrunggeopfert werden können,und wobei δ diefolgende Beziehung zu D aufweist: D = nδ(1 – p)wobein die Vektorlängeund p die erwartete Fehlerhafte-Sektoren-Rateist. Fürden Fall von unabhängigund iden tisch verteilten Defekten wird die optimale Rate von Verzerrungendurch folgendes wiedergegeben:
    [0043] Dieoptimale Größe des Codebuchsist: 2nR(δ) wobei n die Abmessungeines Codevektors ist.
    [0044] Dieoptimale Größe für die Abmessungder Eingangs- und Codewortvektoren n kann ebenfalls optimiert werden.Wenn die Vektorabmessung zu gering ist, kann die Codebucherstellungzu rasch einem nicht-optimalen Codebuch nähern, und die effektive erhältlicheKomprimierungsrate kann zu gering sein. Wenn die Vektorabmessungdagegen zu groß ist,wird die Anzahl von Eingangsvektoren, die bei jeder Iteration des LBG-Algorithmus des Asymmetrische-Verzerrung-Modellsberücksichtigtwerden müssen,untragbar groß,und der Codierungsprozeß kannzu komplex werden. Eine optimale Größe für die Abmessung der Eingangs-und Codewortvektoren n kann durch Versuch-Und-Irrtum-Verfahren bestimmtwerden.
    [0045] Umein effektives Komprimierungs-/Entkomprimierungsverfahren für eine Defekte-Speicherplätze-Tabelleauszuwählen,ist es wünschenswert,in der Lage zu sein, einen Gütefaktorfür diverseKomprimierungs-/Entkomprimierungsverfahren zu berechnen und dasKomprimierungs-/Entkomprimierungsverfahren auszuwählen, dasden besten Gütefaktorerzeugt. Der beste Wert füreinen Gütefaktorkann der ge ringste Wert, der größte Wert,der am nächstenbei 0 liegende Wert oder irgendein anderer Wert sein, je nach der Form,in der der Gütefaktorausgedrücktist. Nachstehend ist ein nützlicherGütefaktorfür Komprimierungs-/Entkomprimierungsverfahrenabgeleitet, der einen größeren Wertfür einwünschenswerteresKomprimierungs-/Entkomprimierungsverfahren erzeugt.
    [0046] EineBetriebs-Ratenverzerrungsfunktion bei vorgeschriebenen VerzerrungenRkomp(δ) für einen gegebenen Komprimierungsalgorithmuskomp wird bei der Ableitung des Gütefaktors verwendet. DieseFunktion bestimmt auf statistische oder deterministische Weise dieBitrate, die durch den Komprimierungsalgorithmus komp, der mit einerFehlerfreie-Zu-Fehlerhafte-Sektoren-Verzerrungsratevon δ arbeitet,erzielt wird. Die Charakterisierung kann alles von einer asymptotischenCharakterisierung übereine Schlimmster-Fall-Charakterisierungbis hin zu einer maximalen Anzahl von codierten Bits sein. In allenFällenmuß dieCharakterisierung die Eigenschaft aufweisen, daß die Komprimierter-Bitstrom-Länge für alle netwa gleich nRkomp(δ) sein sollte, falls der Komprimierungsalgorithmusverwendet wird, um n Bits (wobei sich n von dem zuvor verwendetenn, das die Anzahl von Bits in einem Vektor darstellt, unterscheidet)mit einer Fehlerfreie-Zu-Fehlerhafte-Sektoren-Fehlcharakterisierungsratevon δ zukomprimieren. Falls die Fraktion von fehlerhaften Sektoren p ist,so entsprächedies n(1 – p)δ fehlcharakterisiertenSektoren, die nicht verwendet werden, während die Anzahl von fehlerfreienSektoren, die gemäß der Defekttabelletatsächlichzur Verfügungstehen, n(1 – p)(1 – δ) beträgt.
    [0047] Diefür einSchema einer verlustbehafteten Defekttabellenkomprimierung in Betrachtgezogenen Kosten beinhalten die Kosten/Sektor einer Massenspeicherungund die Kosten/Bit eines schnellen Speichers β. Die Kosten der Gesamtanzahlvon Sektoren einer Massenspeicherung, der Speicherung, für die dieDefekttabelle erstellt und unterhalten wird, mal α plus dieAnzahl von Bits, die durch die Tabelle eingenommen werden, mal β. Die Formelfür dieGesamtkosten C, wenn n Sektoren einer Massenspeicherung vorausgesetztwerden, beträgt: C = αn+ βnRkomp(δ)
    [0048] EinKomprimierungs-/Entkomprimierungsverfahren muß eine Kosteneinschränkung Cmax erfüllen,die wie folgt definiert ist. Cmax > C
    [0049] EinKomprimierungs-/Entkomprimierungsverfahren komp kann bezüglich derVerzerrung δ optimiert werden,indem der Speicher, der durch die komprimierte Defekte-Speicherplätze-Tabelleverwendet wird, innerhalb der Kosteneinschränkung Cmax wiefolgt maximiert wird:
    [0050] Dafür einfeststehendes δ,n maximiert werden sollte, um eine Gleichheit bezüglich derEinschränkung zuerzielen, kann diese Optimierung äquivalent wie folgt ausgedrückt werden:
    [0051] DerBegriff
    [0052] Einweiterer Lösungsansatzbezüglicheiner Komprimierung/Entkomprimierung von Defekte-Speicherplätze-Tabellenbesteht darin, eine Lauflängenquantisierungzu verwenden, eine Technik, die ein weiteres Ausführungsbeispielder vorliegenden Erfindung darstellt. Bei dieser Technik wird einLauflängencodierenverwendet, im Gegensatz zu einem standardmäßigen Lauflängencodieren, wie es oben unterBezugnah me auf 3A–3C erläutert wurde, werden jedochquantisierte Lauflängenverwendet, um zu ermöglichen,daß inder komprimierten Tabelle Indizes statt Ganzzahlen, die die Längen vonLäufenspezifizieren, verwendet werden. 12 und 13 veranschaulichen das Lauflängenquantisierungs-Komprimierungs-/Entkomprimierungsverfahren,das ein Ausführungsbeispielder vorliegenden Erfindung darstellt. 12 zeigtein Array L, das Lauflängenquantenli enthält,wobei i bei dem vorliegenden Beispiel zwischen 0 und 31 liegt. DieLauflängenquanten spezifizierendie Größen vonLäufenvon „0"-Werten, auf dieLäufe von „1"-Werten folgen. Für einengegebenen Lauf von „0"-Werten einer Länge r ineiner unkomprimierten Tabelle wählteine Quantisierungsfunktion Q(r) ein Lauflängenquantum li aus,derart, daß li das größte Quantumin L ist, das kleiner oder gleich r ist. Dann wird die nächste Sequenzvon li + i Werten von der unkomprimiertenTabelle komprimiert, indem die li+1 Wertedurch den Index des Quantums li in dem ArrayL ersetzt werden. Wenn der Index des Quantums li entkomprimiert wird,wird er wiederum durch einen Lauf von li „0"-Werten, auf dieein Lauf von (li+1 – li) „1"-Werten folgt, ersetzt. Eineeffizientere Komprimierung kann erhalten werden, indem eine Variable-Länge-Codierung von quantisiertenLauflängenverwendet wird.
    [0053] 13 zeigt die Lauflängenquantisierungskomprimierungeiner kurzen, beispielhaften Bitfolge. Bei 13 wird die kurze beispielhafte Bitfolge 1302 zuder komprimierten Bitfolge 1304 komprimiert, die wiederumzu der entkomprimierten Bitfolge 1306 entkomprimiert wird.Bei einem ersten Schritt wird der anfängliche Lauf von 1 „0"-Wert 1308 zu dem5-Bit-Index 1310 komprimiert, indem auf die Lauflänge „1" eine QuantisierungsfunktionQ angewendet wird, um l1 als das Quantumzu identifizieren, das einem Lauf der Länge 1 entspricht, das eineneinzigen „0"-Wert darstellt,auf den ein (l2 – l1),oder 1, „1"-Wert folgt. Selbstverständlich führt dieseerste li-basierte Komprimierung in der Tatzu einer Erweiterung und würdebei einem tatsächlichenSy stem allgemein nicht verwendet. Bei einem nächsten Schritt wird ein Laufvon 10 „0"-Werten, wobei mitdem „0"-Wert 1312 begonnenwird, durch einen L-Array-Index „4" 1314, der l4 entspricht,ersetzt. Dies stellt einen Lauf von 10 „0"-Wertendar, auf den ein Lauf von (l5 – l4), oder 4, „1"-Wertenfolgt. Schließlichwird ferner ein Lauf von 12 „0"-Werten durch einen L-Array-Index „4" 1318, derl4 entspricht, ersetzt.
    [0054] EineEntkomprimierung beinhaltet ein Identifizieren jedes L-Array-Indizesi und ein Ersetzen des L-Array-Indizes durch li „0"-Werte, auf die einLauf von (li+1 – li) „1"-Werten folgt. Wie in 13 gezeigt ist, kann eine Verzerrungauftreten. Die „1"-Werte 1320–1324 inder entkomprimierten Bitfolge 1306 waren ursprünglich „0"-Werte in der unkomprimiertenBitfolge 1302. Somit stellt eine Lauflängenquantisierung eine verlustbehafteteKomprimierung mit einer asymmetrischen Verzerrung dar, wie in demFall einer Vektorquantisierung.
    [0055] FallsLauflängenr nicht-defekter Blöckegemäß der Wahrscheinlichkeitsverteilungp(r) zufälligauftreten, so ist die durchschnittliche oder erwartete Fehlerfreie-Zu-Fehlerhafte-Sektoren-Fehlkennzeichnungsrate, diedurch Verwendung einer Partitionierung
    [0056] 14 und 15 liefern in dem Format eines Ablaufsteuerungsdiagrammseine Übersicht über einVerfahren zum Bereitstellen eines Speichers, das eines der beschriebenenAusführungsbeispieleder vorliegenden Erfindung beinhaltet. 14 veranschaulicht ein allgemeines Verfahrenzum Bereitstellen eines Speichers, der eine Defekte-Datenspeicherplätze-Tabellebeinhaltet, die gemäß einemder beschriebenen Ausführungsbeispieleder vorliegenden Erfindung komprimiert ist bzw. wird. Bei Schritt 1402 wirdeine Defekte-Datenspeicherplätze-Tabelleerstellt. Wie oben erläutertwurde, ist eine Bittabellenimplementierung für eine Defekte-Datenspeicherplätze-Tabellezweckmäßig, wobeijedes Bit einen Datenspeicherplatz darstellt. Ein Datenspeicherplatzkann z.B. ein Plattenblock oder ein Plattensektor sein oder kann,als weiteres Beispiel, ein oder mehrere Nanodraht-Array-Übergänge in einemnanodrahtbasierten Speicher sein. Bei Schritt 1404 wirddie Defekte-Datenspeicherplätze-Tabelleunter Verwendung einer verlustbehafteten Komprimierungstechnik,beispielsweise einer der oben erläuterten verlustbehafteten Techniken,komprimiert. Man beachte, daß verlustbehafteteKomprimierungstechniken bezüglichder vorliegenden Erfindung keine einfachen Änderungen der Granularität der Defekte-Datenspeicherplätze- Tabelle umfassen,beispielsweise ein Verwenden eines einzelnen Bits, um einen Plattensektorstatt eines Plattenblocks darzustellen. Bei der Schleife, die dieSchritte 1406–1409 aufweist,werden logische Datenspeicherplatz-Zugriffsanforderungen erhalten und gehandhabt.Ein ausreichender Anteil der Defekte-Datenspeicherplätze-Tabellewird bei Schritt 1407 entkomprimiert, um einen entsprechendenphysischen Datenspeicherplatz zu bestimmen, der dem angefordertenlogischen Datenspeicherplatz entspricht, und der physische Datenspeicherplatzwird verwendet, um Daten von dem Datenspeicherplatz wiederzuerlangenoder Daten in denselben zu schreiben.
    [0057] 15 veranschaulicht ein verlustbehaftetesKomprimierungsverfahren, das bei Schritt 1404 der 14 aufgerufen wird. BeiSchritt 1502 wird ein anfängliches Codebuch erstellt,in dem ein Codewort fürjede einer Anzahl von Partitionen ausgewählt wird, wie oben erläutert wurde.Bei Schritt 1504 wird der Vektorraum von Vektoren, in diedie Defekte-Datenspeicherplätze-Tabellezerlegt wird, partitioniert, um ein abschließendes Codebuch er erzeugen.Bei der für-Schleife,die die Schritte 1506–1509 umfaßt, wirddie Defekte-Datenspeicherplätze-Tabelleanschließendin Vektoren einer feststehenden Länge zerlegt, und für jedenVektor einer feststehenden Längewird der Index der Codebuchpartition, die den Vektor enthält, vondem Codebuch wiedererlangt und zu der komprimierten Tabelle hinzugefügt, wieoben erläutertwurde.
    [0058] Obwohldie vorliegende Erfindung anhand eines bestimmten Ausführungsbeispielsbeschrieben wurde, ist nicht beabsichtigt, daß die Erfindung auf diesesAusführungsbeispielbeschränktsei. Fachleuten werden Modifikationen einfallen, die in der Wesensartder Erfindung enthalten sind. Wie oben erläutert wurde, kann beispielsweiseder Gütefaktorzum Vergleichen der Effizienz verschiedener Defekte-Speicherplätze-Tabellen-Komprimierungs-/Entkomprimierungsverfahrenmathematisch umgeformt werden, um eine größere Effizienz anzugeben, indemWerte erzeugt werden, die näherbei 0 liegen oder eine geringere Größe aufweisen, statt größere Wertezu erzeugen. Verschiedene alternative Gütefaktoren können erhaltenwerden, indem zusätzlicheoder andere Beschränkungenaufgenommen werden und indem die Effizienz bezüglich verschiedener Parametermaximiert wird. Währendsich Vektorquantisierungs- und Lauflängenquantisierungsverfahren für vieleDefekte-Speicherplätze-Verteilungenals sehr effizient und nützlicherwiesen haben, könnenandere Komprimierungs-/Entkomprimierungsverfahren identifiziertwerden, die fürandere Defekte-Speicherplätze-Verteilungen nützlichersind. Variationen bei diesen Verfahren sind möglich und beinhalten VariationenbezüglichImplementierung, Sprache und Implementierungsstil, der Behandlungvon Grenzbedingungen, der Codebuchstruktur, Datenstrukturen, desSinns und der Bedeutung bestimmter Bitwerte sowie viele andere Variationen.Allgemein erfordert jeder Speicherplatzzugriff eine Entkomprimierungeiner komprimierten Defekte-Speicherplätze-Tabelle, um die physischeAdresse des Speicherplatzes, auf den zugegriffen wird, zu bestimmen.Jedoch kann es möglichsein, die Tabelle in Segmente zu komprimieren und einen Index indiese Segmente bereitzustellen, um eine Entkomprimierung lediglicheines relevanten Abschnitts der Tabelle zu ermöglichen, statt zu erfordern,daß diegesamte Tabelle entkomprimiert wird.
    权利要求:
    Claims (20)
    [1] Verfahren zum Liefern einer geordneten Sequenzvon nicht-defekten Speicherplätzen,wobei das Verfahren folgende Schritte aufweist: Erstellen (1402)einer Defekte-Datenspeicherplätze-Tabelle (201, 207, 402); Komprimieren(1404), mittels einer verlustbehafteten Komprimierung,der Defekte-Datenspeicherplätze-Tabelle(402) zu einer komprimierten Defekte-Datenspeicherplätze-Tabellemittels eines anderen verlustbehafteten Komprimierungsverfahrens(602, 604, 700) als einem Ändern einerDatenspeicherplatzgröße, derEinträgein die Defekte-Datenspeicherplätze-Tabelleentsprechen; und wenn durch eine logische Adresse auf einenDatenspeicherplatz zugegriffen wird, Entkomprimieren (1407)eines ausreichenden Abschnitts der Defekte-Datenspeicherplätze-Tabelle,um einen physischen Platz (1408) des logisch adressiertenDatenspeicherplatzes zu bestimmen.
    [2] Verfahren gemäß Anspruch1, bei dem das Entkomprimieren (1407) eines ausreichendenAbschnitts der Defekte-Datenspeicherplätze-Tabelle,um einen physischen Platz des logisch adressierten Datenspeicherplatzeszu bestimmen, ferner folgende Schritte umfaßt: Extrahieren von Indizes(1310, 1314, 1318) aus der komprimiertenDefekte-Datenspeicherplätze-Tabelle;und Einfügen,für jedenextrahierten Index, des Codeworts, das dem Index in dem Codebuchzugeordnet ist, in eine entkomprimierte Defekte-Datenspeicherplätze-Tabelle.
    [3] Verfahren gemäß Anspruch1 oder 2, bei dem die Defekte-Datenspeicherplätze-Tabelle (201, 207, 402) eineBittabelle aufweist, bei der jedes Bit angibt, ob ein entsprechenderphysischer Datenspeicherplatz defekt ist oder nicht.
    [4] Verfahren gemäß Anspruch3, bei dem das Komprimieren der Defekte-Datenspeicherplätze-Tabelleund das Speichern der komprimierten Defekte-Datenspeicherplätze-Tabelle ferner folgendeSchritte umfaßt: Erstelleneines anfänglichenCodebuchs (1502), das einen Satz von Codewörtern aufweist,wobei jedes Codewort einen Bitvektor aufweist, der eine Länge vonn Bits aufweist; Partitionieren von Eingangsvektoren (1504)in diskrete Partitionen, wobei jede Partition ein einzelnes Codewortumfaßtund eine Partition ein Codewort umfaßt, das n Bitwerte aufweist,die defekte Speicherplätzeangeben, um ein Codebuch zu erzeugen; und Extrahieren aufeinanderfolgenderEingangsvektoren (1507-1508), die Längen von n Bits aufweisen,aus der Defekte-Datenspeicherplätze-Tabelle,und Plazieren, fürjeden extrahierten Eingangsvektor, eines Index des Codeworts ineiner Codebuchpartition, die den extrahierten Eingangsvektor umfaßt, in diekomprimierte Defekte-Datenspeicherplätze-Tabelle.
    [5] Verfahren gemäß Anspruch4, bei dem das Plazieren, fürjeden extrahierten Eingangsvektor, eines Index des Codeworts ineiner Codebuchpartition, die den extrahierten Eingangsvektor umfaßt, in diekomprimierte Defekte-Datenspeicherplätze-Tabelle ferner ein Bestimmender Codebuchpartition, die den extrahierten Eingangsvektor umfaßt, durcheines der folgenden umfaßt: einenTabellennachschlag; Berechnen der Codebuchpartition unter Verwendungeiner Abstandsmetrik; und Berechnen der Codebuchpartition unterVerwendung einer Verzerrungsmetrik.
    [6] Verfahren gemäß Anspruch5, bei dem das Erstellen eines Codebuchs, das einen Satz von Codewörtern aufweist,ferner ein Verwenden eines LBG-Algorithmus eines Asymmetrische-Verzerrung-Modells,durch den ein anfänglichausgewählterSatz von Codewörterniterativ modifiziert wird (1106, 1008, 1109,1113), umfaßt.
    [7] Verfahren gemäß Anspruch6, bei dem die Gesamtverzerrung als eine Summe von Verzerrungenin jeder Partition jedes Eingangsvektors bezüglich des Codeworts für die Partitionberechnet wird.
    [8] Verfahren gemäß Anspruch7, bei dem die Verzerrung D zwischen einem Eingangsvektor x ^ und einem Codewortx als eine asymmetrische Verzerrung
    [9] Verfahren gemäß einemder Ansprüche4 bis 8, bei dem das Erstellen eines Codebuchs, das einen Satz vonCodewörternaufweist, ferner ein zufälligesErzeugen der Codewörtergemäß einerWahrscheinlichkeitsverteilung umfaßt.
    [10] Verfahren gemäß Anspruch9, das ferner ein Verwenden jedes Index jeder Partition als Keimfür einen Pseudozufallsgenerator,um Codewörterzu erzeugen, umfaßt.
    [11] Verfahren gemäß Anspruch10, bei dem das Entkomprimieren (1407) eines ausreichendenAbschnitts der Defekte- Datenspeicherplätze-Tabelle,um einen physischen Platz des logisch adressierten Datenspeicherplatzeszu bestimmen, ferner folgende Schritte umfaßt: Extrahieren von Indizesaus der komprimierten Defekte-Datenspeicherplätze-Tabelle; Liefernjedes extrahierten Index an den Pseudozufallsgenerator, um entsprechendeentkomprimierte Codewörterzu erzeugen; und Einfügender entkomprimierten Codewörterin eine entkomprimierte Defekte-Datenspeicherplätze-Tabelle.
    [12] Verfahren gemäß einemder Ansprüche2 bis 11, bei dem das Komprimieren (1404) der Defekte-Datenspeicherplätze-Tabelleferner folgende Schritte umfaßt: Lieferneiner Quantisierungsfunktion Q (1008), die für einenLauf von identischen Bitwerten einer Länge r ein Quantum li, das kleiner oder gleich r ist, von einemgeordneten Satz L von Quanten zurückgibt, die mit einer ansteigendenPosition i innerhalb des geordneten Satzes L streng an Größe zunehmen; anschließendes Extrahiereneines Laufs von Bits mit identischen Werten aus der Defekte-Datenspeicherplätze-Tabelle,beginnend bei einer Position j in der Defekte-Datenspeicherplätze-Tabelle,wobei der anfängliche Wertvon j gleich 0 ist, und, fürjeden extrahierten Lauf von Bits mit identischen Werten: Anwendender Quantisierungsfunktion Q auf die Länge des extrahierten Laufes,um ein Quantum li, das der Länge desLaufs entspricht, auszuwählen, Plazierendes Index i in die komprimierte Defekte-Datenspeicherplätze-Tabelle;und Vorrückenvon j um li+1 Positionen.
    [13] Verfahren gemäß Anspruch12, bei dem das Entkomprimieren (1407) eines ausreichendenAbschnitts der Defekte-Datenspeicherplätze-Tabelle,um einen physischen Platz des logisch adressierten Datenspeicherplatzeszu bestimmen, ferner folgende Schritte umfaßt: Extrahieren von Indizesaus der komprimierten Defekte-Datenspeicherplätze-Tabelle; für jedenextrahierten Index i: Plazieren eines Quantums von li Bits mit identischen Werten, auf die einQuantenunterschied von (li+i – li) Bits mit entgegengesetzten Werten folgt,in eine entkomprimierte Defekte-Datenspeicherplätze-Tabelle.
    [14] Verfahren zum Vergleichen von Verfahren zum Komprimiereneiner Defekte-Speicherplätze-Tabellezu einer komprimierten Defekte-Speicherplätze-Tabelle, wobei das Verfahrenfolgende Schritte aufweist: Liefern eines Kosten/Bit-Parametersfür dieBittabelle; Liefern eines Kosten/Bit-Parameters β für die komprimierteBittabelle; Bestimmen, fürjedes Verfahren zum Komprimieren einer Bittabelle, komp, einer Betriebs-RatenverzerrungsfunktionRkomp(δ) Berechnen eines GütefaktorsF für jedesVerfahren zum Komprimieren einer Bittabelle; und Auswählen einesVerfahrens zum Komprimieren einer Bittabelle mit einem wünschenswertestenGütefaktorF.
    [15] Verfahren gemäß Anspruch14, bei dem der Gütefaktorals
    [16] Speicher, der folgende Merkmale aufweist: eineSpeichervorrichtung mit physischen Speicherplätzen (101–109);und eine komprimierte (1404) Defekte-Speicherplätze-Tabelle, die aufeinen Zugriff eines logischen Speicherplatzes in dem Speicher hinentkomprimiert wird (1407), um den logischen Speicherplatzauf einen physischen Speicherplatz abzubilden.
    [17] Speicher gemäß Anspruch16, bei dem die Defekte-Speicherplätze-Tabelleeine Bittabelle (201, 207, 402) umfaßt, beider jedes Bit angibt, ob ein entsprechender physischer Speicherplatzdefekt ist oder nicht.
    [18] Speicher gemäß Anspruch17, bei dem die komprimierte Defekte-Speicherplätze-Tabelle Indizes (1310, 1314, 1318)von Codewörternin einem Codebuch aufweist, wobei ein einzelnes Codewort in jedereiner Anzahl von Partitionen ein Codewort und zusätzlicheEingangsvektoren umfaßt.
    [19] Speicher gemäß Anspruch18, bei dem jedes Codewort und jeder Eingangsvektor ein Bitvektormit einer Längevon n Bits ist, wobei Eingangsvektoren nacheinander aus einer anfänglichen,unkomprimierten Defekte-Speicherplätze-Tabelle (402)extrahiert werden.
    [20] Speicher gemäß einemder Ansprüche17 bis 19, bei dem die komprimierte Defekte-Speicherplätze-TabelleIndizes von Quanten innerhalb eines geordneten Satzes L von Quantenaufweist, die mit einer ansteigenden Position i innerhalb des geordnetenSatzes L streng an Größe zunehmen.
    类似技术:
    公开号 | 公开日 | 专利标题
    US9503123B1|2016-11-22|Random access to compressed data using bitwise indices
    US20200117536A1|2020-04-16|Data Storage System and Method for Decoding Data based on Extrapolated Flipped-Bit Data
    US9007828B2|2015-04-14|Methods and apparatus for storing data in a multi-level cell flash memory device with cross-page sectors, multi-page coding and per-page coding
    US8972674B2|2015-03-03|Compensation for solid state storage
    US9448882B2|2016-09-20|Systems and methods for enhanced data recovery in a solid state memory system
    KR101458441B1|2014-11-07|플래시 메모리로부터 판독된 하드 비트 및 소프트 비트의 소프트 디코딩
    Jegou et al.2010|Product quantization for nearest neighbor search
    US6279133B1|2001-08-21|Method and apparatus for significantly improving the reliability of multilevel memory architecture
    KR101176433B1|2012-08-30|복호 장치 및 방법, 및 프로그램
    KR20160013843A|2016-02-05|판독 전압들의 업데이트
    CN101876947B|2012-05-23|用于存储数据的方法及其系统
    US7149949B2|2006-12-12|Method for error correction decoding in a magnetoresistive solid-state storage device
    JP4091990B2|2008-05-28|データ符号化ネットワーク
    US5883588A|1999-03-16|Data compression system and data compression device for improving data compression rate and coding speed
    Dong et al.2013|Enabling NAND flash memory use soft-decision error correction codes at minimal read latency overhead
    US7102552B1|2006-09-05|Data compression with edit-in-place capability for compressed data
    US20130258738A1|2013-10-03|Optimized threshold search in analog memory cells using separator pages of the same type as read pages
    US6484142B1|2002-11-19|Encoder using Huffman codes
    KR101618925B1|2016-05-09|고착 고장을 갖는 메모리 셀에 비트를 저장하기 위한 기법
    Williams et al.1999|Compressing integers for fast file access
    US6526538B1|2003-02-25|Turbo product code decoder
    TWI501238B|2015-09-21|藉由調變編碼用於單元間干擾抑制的方法及裝置
    KR101422050B1|2014-07-23|셀 당 멀티­비트인 플래시 메모리에서의 오류 보정 방법
    US8838551B2|2014-09-16|Multi-level database compression
    US6836225B2|2004-12-28|Fast search method for nearest neighbor vector quantization
    同族专利:
    公开号 | 公开日
    US7013378B2|2006-03-14|
    US20040221192A1|2004-11-04|
    JP3978195B2|2007-09-19|
    JP2004334846A|2004-11-25|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    2004-12-09| OP8| Request for examination as to paragraph 44 patent law|
    2006-11-16| 8139| Disposal/non-payment of the annual fee|
    优先权:
    申请号 | 申请日 | 专利标题
    [返回顶部]